package com.itheima.datastructure.binarysearchtree;

import com.itheima.datastructure.binarysearchtree.binarytree.TreeNode;

import java.util.LinkedList;
import java.util.concurrent.atomic.AtomicLong;

//判断是否为合法的二叉搜索树
public class E04Leetcode98 {
    //采用中序遍历实现
    public boolean isValidBST1(TreeNode node) {
        TreeNode p = node;
        LinkedList<TreeNode> stack = new LinkedList<>();
        long prev = Long.MIN_VALUE;
        while (p != null || !stack.isEmpty()) {
            if (p != null) {
                stack.push(p);
                p = p.left;
            } else {
                TreeNode pop = stack.pop();
                //处理值
                if (prev >= pop.val) {
                    return false;
                }
                prev = pop.val;
                ;
                p = pop.right;
            }
        }
        return true;
    }

    //递归实现
    long prev=Long.MIN_VALUE;
    public boolean isValidBST2(TreeNode node){
        if(node==null){
            return true;
        }
        boolean a=isValidBST2(node.left);
        //如果左子树不行，右子树不用遍历了，直接返回false（剪枝）
        if(!a){
            return false;
        }
        //值
        if(prev>=node.val){
            return false;
        }

        return isValidBST2(node.right);
    }

    //递归实现
    public boolean isValidBST3(TreeNode node){
        return doValid3(node,new AtomicLong(Long.MIN_VALUE));
    }
    private boolean doValid3(TreeNode node, AtomicLong prev){
        if(node==null){
            return true;
        }
        boolean a=doValid3(node.left,prev);
        if(!a){
            return false;
        }
        if(prev.get()>=node.val){
            return false;
        }
        prev.set(node.val);
        return doValid3(node.right,prev);
    }

    //上下限递归
    public boolean isValidBST4(TreeNode node){
        return doValid4(node,Long.MIN_VALUE,Long.MAX_VALUE);
    }
    private boolean doValid4(TreeNode node,long min,long max){
        if(node==null){
            return true;
        }

        if(node.val<=min ||node.val>=max){
            return false;
        }
        return doValid4(node.left,min,node.val) && doValid4(node.right,node.val,max);
    }
}